Collection of Tools & Utilities/Collection of Tools and Utilities.iso/tex/ddjgrep.zip/QUEUE.C

Text File | 1987-11-04 | 5KB | 207 lines

#ifdef DEBUG
#include <stdio.h>
#endif

/*-------------------------------------------------------------------
 *    QUEUE.C:    General purpose queue management routines:
 *
 *     Copyright (c) 1985, Allen I. Holub.  All rights reserved
 *  This program may be copied for personal, non-profit, use only.
 *-------------------------------------------------------------------
 *
 *  The QUEUE data structure. No external routine needs to know anything
 *  about how this structure is put together. These routines need only
 *  remember a pointer to the queue (in a manner similar to the FILE
 *  pointer used by the i/o routines).
 */

typedef struct
{
    char    *start;        /* Pointer to beginning of queue    */
    int    head;        /* Index of current head         */
    int    tail;        /* Index of current tail         */
    int    size;        /* Max num of objects queue can hold    */
    int    nobj;        /* Number of objects now in the queue    */
    int    objsize;    /* Size of one element             */
} QUEUE;

/*----------------------------------------------------------------------*/

QUEUE    *makequeue( qsize, objsize )
{
    /* Make a queue of the specified size containing objects of the
     * specified size. Return a pointer to the queue or 0 if there is
     * not enough memory to make the queue. Queues are created using
     * calloc(). They require sizeof(QUEUE) + (qsize * objsize) bytes.
     */

    register QUEUE    *qp;

    if( !(qp = (QUEUE *) malloc(sizeof(QUEUE) + (qsize * objsize)) ))
        return 0;

    qp->start     = (char *)(qp + 1);
    qp->size     = qsize   ;
    qp->objsize    = objsize ;

    qp->head = qp->tail = qp->nobj = 0;

    return( qp );
}

del_queue( qp )
QUEUE    *qp;
{
    /*   Delete a queue and free the memory. The queue will NOT
     *   be deleted unless it is empty. Return 1 if the queue
     *   was deleted, 0 otherwise. If you don't care if the queue
     *   is actually empty, use free(qp).
     */

    if( qp->nobj )
        return 0;

    free( qp );
    return 1;
}

/*----------------------------------------------------------------------*/

enqueue( obj, qp )
char    *obj ;
QUEUE    *qp  ;
{
    /*    Put an object into the queue. Obj is a pointer to the
     *    object qp is a pointer to a QUEUE. Return 1 on success,
     *    0 if there's no more room in the queue.
     */

    int    i;                /* Counter        */
    char    *bp;                /* points into queue    */

    if( qp->nobj  >=  qp->size )        /* If the queue is full */
        return 0;            /* return failure.    */

    qp->nobj++;                /* One more object in    */
                        /* the queue        */

    bp= qp->start + (qp->objsize * qp->tail); /* Get target address */
                        /* within the queue;    */
                        /* then    move object     */
                        /* into it:        */

    for( i = qp->objsize;  --i >= 0;  *bp++ = *obj++ )
        ;

    if( ++qp->tail >= qp->size)         /* Wrap around if we've    */
        qp->tail = 0;            /* gone off the end of    */
                        /* the queue.        */
    return 1;
}

dequeue( obj, qp )
char    *obj ;
QUEUE    *qp  ;
{
    /*    Get an object from the queue. Qp is a pointer to a QUEUE,
     *    The dequeued object is copied into the place pointed to by
     *    obj. Return 0 if the queue is empty and no object was
     *    dequeued, 1 otherwise.
     */

    register int    i;
    register char    *bp;

    if( qp->nobj <= 0 )
        return 0;                /* queue empty */

    qp->nobj-- ;

    bp = qp->start + (qp->objsize * qp->head) ;

    for( i = qp->objsize; --i >= 0; *obj++ = *bp++ )
        ;

    if( ++qp->head >= qp->size )
        qp->head = 0;

    return 1;
}

/*----------------------------------------------------------------------*/
/*  Little access routines:                        */
/*    Show_next returns a pointer to the object at the head of the    */
/*    queue; sp_used returns the number of objects in the queue    */
/*    sp_avail returns the number of slots available in the queue.    */

char    *show_next (qp)
QUEUE    *qp;
{
    return( qp->start + (qp->head * qp->objsize)  );
}

int    sp_used    (qp)
QUEUE    *qp;
{
    return( qp->nobj );
}

int    sp_avail   (qp)
QUEUE    *qp;
{
    return( qp->size - qp->nobj );
}

#ifdef DEBUG

main()
{
    int    num, c, *ip;
    QUEUE    *qp;

    qp = makequeue( 4, sizeof(int) );

    while( 1 )
    {
        num = c = -1;

        ip = (int *)qp->start ;

        printf("\n\nqueue: %d %d %d %d\n",ip[0],ip[1],ip[2],ip[3]);

        printf("start      =0x%x\n",    qp->start    );
        printf("head      =%d\n",    qp->head    );
        printf("tail      =%d\n",    qp->tail    );
        printf("size      =%d\n",    qp->size    );
        printf("objsize   =%d\n",    qp->objsize     );
        printf("nobj      =%d\n",    qp->nobj    );

        printf("there are %d slots left in the queue\n\n",
                            sp_avail(qp) );

        printf("(d/e/q) ->");
        while( c != 'e' && c != 'd' && c != 'q' )
            c = getchar();

        if( c == 'e' )
        {
            printf("enter decimal number ->");
            scanf("%d", &num );
            printf("enqueue(%d) returned %d\n",
                        num, enqueue(&num,qp) );
        }
        else if( c == 'd' )
        {
            printf( "dequeue returned %d, loaded %d\n",
                        dequeue( &num, qp ), num );
        }
        else
            break;
    }

    printf(" deleting queue, queue was %sempty\n",
                    del_queue(qp) ? "" : "not " );
}

#endif